package com.cg.leetcode;

import org.junit.Test;

/**
 * 968.监控二叉树
 *
 * @author cg
 * @program LeetCode->LeetCode_968
 * @create 2022-09-12 22:04
 **/
public class LeetCode_968 {

    @Test
    public void test968() {
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(0);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(0);
        System.out.println(minCameraCover(root));
    }

    /**
     * 给定一个二叉树，我们在树的节点上安装摄像头。
     * 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
     * 计算监控树的所有节点所需的最小摄像头数量。
     * <p>
     * 示例 1：
     * 输入：[0,0,null,0,0]
     * 输出：1
     * 解释：如图所示，一台摄像头足以监控所有节点。
     * <p>
     * 示例 2：
     * 输入：[0,0,null,0,null,0,null,null,0]
     * 输出：2
     * 解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
     * <p>
     * 提示：
     * 给定树的节点数的范围是 [1, 1000]。
     * 每个节点的值都是 0。
     *
     * @param root
     * @return
     */
    public int minCameraCover(TreeNode root) {
        // 判断根节点是否无覆盖
        if (helper(root) == 0) {
            result++;
        }
        return result;
    }

    int result = 0;

    /**
     * 节点的状态值：
     * 0 表示无覆盖
     * 1 表示有摄像头
     * 2 表示有覆盖
     * 后序遍历
     * @param root
     * @return
     */
    private int helper(TreeNode root) {
        // 空节点，默认有覆盖状态，避免在叶子节点上放摄像头
        if (root == null) {
            return 2;
        }
        int left = helper(root.left);
        int right = helper(root.right);
        // 左右节点有无覆盖状态，那么根节点要放一个摄像头
        // (0,0),(0,1),(0,2),(1,0),(2,0)
        if (left == 0 || right == 0) {
            result++;
            return 1;
        } else if (left == 2 && right == 2) {
            // 左右节点都覆盖了，那么本节点就是无覆盖状态，没有摄像头
            // (2,2)
            return 0;
        } else {
            // 左右节点至少有一个存在摄像头，那么本节点就是处于被覆盖状态
            // (1,1),(1,2),(2,1)
            return 2;
        }
    }

}
